#include<iostream>
using namespace std;
class intList {
protected:
    struct Node {
        Node *next;
        int data;
    };
    Node *pFirst;
public:
    intList();
    ~intList();
    bool insert(int i, int elem);
    bool remove(int i, int &elem);
    int find(int elem) const;
    int length() const;
    void printList();
};

intList::intList() {
    pFirst = new Node;
    pFirst->next = NULL;
};

intList::~intList() {
    Node *p, *q;
    p = pFirst;
    while (p->next != NULL) {
        q = p->next;
        delete p;
        p = q;
    }
    delete p;
    pFirst = NULL;
}

int intList::length() const {
    Node *p;
    int j;
    p = pFirst->next;
    j = 0;
    while (p != NULL) {
        p = p->next;
        j++;
    }
    return j;
}

int intList::find(int elem) const {
    Node *p;
    int j;
    int data;
    p = pFirst->next;
    j = 1;
    while (p != NULL) {
        data = p->data;
        if (data == elem)break;
        p = p->next;
        j = j + 1;
    }
    if (p != NULL)return (j);
    else return (0);
}

bool intList::insert(int loc, int elem) {
    Node *p, *s;
    int j;
    p = pFirst;
    j = 0;
    while ((p != NULL) && (j < loc - 1)) {
        p = p->next;
        j = j + 1;
    }
    if ((p != NULL) && (j == loc - 1)) {
        s = new Node;
        s->data = elem;
        s->next = p->next;
        p->next = s;
        return true;
    } else return false;
}

bool intList::remove(int i, int &elem) {
    Node *p, *q;
    int j;
    p = pFirst;
    j = 0;
    while ((p->next != NULL) && (j < i - 1)) {
        p = p->next;
        j = j + 1;
    }
    if ((p->next != NULL) && (j == i - 1)) {
        q = p->next;
        p->next = p->next->next;
        elem = q->data;
        delete (q);
        return true;
    } else return false;
}

void intList::printList() {
    Node *p;
    p = pFirst->next;
    while (p != NULL) {
        cout << p->data << "";
        p = p->next;
    };
    cout << endl;
}

int main() {
    intList L;
    for (int i = 1; i < 10; i++)
        L.insert(i, i);
    L.printList();
    int el;
    if (L.remove(4, el))
        cout << "Delete the fourth element success!" << endl;
    else
        cout << "delete fail!" << endl;
    L.printList();
    int loc = L.find(5);
    if (loc != 0)
        cout << "Find!The position of Element 5 is" << loc << endl;
    else
        cout << "Not find!" << endl;
    return 0;
}
